package cg.studio.practise;

public class Palindrome
{
  public static void main( String[] arg )
  {
    char[] a = { 'a','a', 'b', 'a','a' };
    System.out.println( palindromeSize(a) );
    System.out.println( palindrome(a) );
    
    char[] b = { 'a','a', 'a', 'a','a' };
    System.out.println( palindromeSize(b) );
    System.out.println( palindrome(b) );
    
    char[] c = { 'c', 'a','a', 'b', 'a','a','d' };
    System.out.println( palindromeSize(c) );
    System.out.println( palindrome(c) );

    char[] d = { 'c', 'a','c', 'b', 'a','a','b' };
    System.out.println( palindromeSize(d) );
    System.out.println( palindrome(d) );
  }

  public static int palindromeSize( char[] a )
  {
    if( a == null || a.length==0 )
      return 0;
    if( a.length == 1 )
      return 0;
    
    int left=0;
    int right=0;
    int size=1;
    
    int maxSize = 0;
    for( int i=0; i<a.length-1; ++i )
    {
      //aba
      if( i+2 < a.length && a[i] == a[i+2])
      {
        size = 3;
        left = i;
        right = i+2;
      }
      //aa
      else if( a[i] == a[i+1] )
      {
        size = 2;
        left = i;
        right = i+1;
      }
      else
        continue;
      
      //expand to both sides
      --left;
      ++right;
      while( left >=0 && right < a.length && a[left]==a[right] )
      {
        size+=2;

        //for next loop
        --left;
        ++right;
      }
      if( size > maxSize )
      {
        maxSize = size;
      }
    }
    return maxSize;
  }
  
  
  public static String palindrome( char[] a )
  {
    if( a == null || a.length==0 || a.length==1 )
      return new String(a);
    

    int maxLeft = 0;
    int maxRight = 0;
    int maxSize = 1;
    for( int i=0; i<a.length-1; ++i )
    {
      int left=0;
      int right=0;
      int size=1;
      
      //aba
      if( i+2 < a.length && a[i] == a[i+2])
      {
        size = 3;
        left = i;
        right = i+2;
      }
      //aa
      else if( a[i] == a[i+1] )
      {
        size = 2;
        left = i;
        right = i+1;
      }
      else
        continue;
      
      //expand to both sides
      --left;
      ++right;
      while( left >=0 && right < a.length && a[left]==a[right] )
      {
        size+=2;

        //for next loop
        --left;
        ++right;
      }
     
      if( size > maxSize )
      {
        //largest size, keep environment
        maxSize = size;
        //left and right already move to next, should fix it
        maxLeft = ++left;
        maxRight = --right;
      }
    }
    return new String( a, maxLeft, maxRight-maxLeft+1 );
  }
}
